import collections
from typing import Optional

from python.mypackage import TreeNode


class Solution:

    """
    方法：DFS递归遍历二叉树，从根节点到叶子节点的路径上的数字组成一个数值，计算所有路径数值的和
    
    Args:
        root: Optional[TreeNode] - 二叉树的根节点
        
    Returns:
        int - 所有从根到叶子节点路径组成的数字之和
        
    Time: O(N) - N为节点数，需要遍历所有节点
    
    Space: O(H) - H为树的高度，递归调用栈的空间
    """

    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root: TreeNode, prevTotal):
            if not root:
                return 0
            total = prevTotal * 10 + root.val
            if not root.left and not root.right:
                return total
            else: 
                return dfs(root.left, total) + dfs(root.right, total)
        return dfs(root, 0)

    """
    方法： sumNumbers1 使用队列进行迭代遍历，计算从根到叶子节点路径组成的数字之和
    
    Args:
        root: Optional[TreeNode] - 二叉树的根节点
        
    Returns:
        int - 所有从根到叶子节点路径组成的数字之和
        
    Time: O(N) - N为节点数，需要遍历所有节点
    
    Space: O(W) - W为树的最大宽度，队列中最多存储一层的节点数
    """
    def sumNumbers1(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        total = 0
        nodeQueue = collections.deque([root])
        numQueue = collections.deque([root.val])

        while nodeQueue:
            node = nodeQueue.popleft()
            num = numQueue.popleft()
            left, right = node.left, node.right
            if not left and not right:
                total += num
            else:
                if left:
                    nodeQueue.append(left)
                    numQueue.append(num * 10 + left.val)
                if right:
                    nodeQueue.append(right)
                    numQueue.append(num * 10 + right.val)
        return total

        